/*
 * @lc app=leetcode.cn id=155 lang=cpp
 *
 * 
 */

// @lc code=start

#include <iostream> // std::cout
#include <stack>    // std::stack
#include <vector>
using namespace std;
class Solution
{

public:
  bool IsPopOrder(vector<int> pushV, vector<int> popV)
  {
    if (pushV.empty() || popV.empty())
    {
      return false;
    }

    stack<int> s;

    // 用于标识弹出序列的位置
    int popIndex = 0;
    // 扫描入栈序列
    for (int i = 0; i < pushV.size(); i++)
    {
      // push元素直到栈顶元素为pop序列中的元素
      s.push(pushV[i]);

      // 相等时，辅助栈出栈，弹出序列索引加一
      while (!s.empty() && s.top() == popV[popIndex])
      {
        s.pop();
        popIndex++;
      }
    }

    return s.empty();
  }
};

int main()
{
  Solution solute;
  vector<int> pushV = {1, 2, 3, 4, 5};
  vector<int> popV = {4, 5, 3, 2, 1};
  int i = solute.IsPopOrder(pushV, popV);
  cout << "i:" << i << endl;
  return 0;
}

// @lc code=end
